package class_0827UnionFindSet;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;

/**
 * 并查集是什么呢？
 * 它是数组，链表，树，哈希表，图经过抽象建模得到的极其nb的结构。
 *
 */

/**
 * 传说中的并查集结构。
 * 路径压缩（Path Compression）和按大小合并（Union by Size）策略
 * 合并和查找时间复杂度可以认为是O(1),实际里面是bigO里面是反阿克曼函数。为什么？看数学推导.
 * 什么情况可以认为时间复杂度是O(n)呢？ 样本量 10^80个数据量。
 * 现在进度太慢了，提醒一句话，看算法导论课和书籍，去看一遍推导过程。
 * @author 90774
 */
public class Coding_UnionFindCode {
    public static class Element<V>{
        V value;
        public Element(V value){
            this.value = value;
        }
    }
    /**
     *
     * @param <V>  元素类型
     */
    public static class UnionFindSet<V>{
        //3个哈希表搞定完结。

        //将元素封装成集合
        public HashMap<V,Element<V>> ElemMap;
        //跟踪父亲节点
        public HashMap<Element<V>,Element<V>> fatherMap;
        //存储集合的数据大小
        public HashMap<Element<V>,Integer>  sizeMap;

        /**
         * 给定一个有序表将其封装成并查集。
         * 时间复杂度：O(N).
         * @param list---有序表（实现list接口的均可）可以改成Collection接口，这样可以放栈，队列，堆了.
         */
        public UnionFindSet(List<V> list) {
            ElemMap = new HashMap<V, Element<V>>();
            fatherMap = new HashMap<Element<V>, Element<V>>();
            sizeMap = new HashMap<Element<V>, Integer>();
            for (var value : list) {
                Element<V> elem = new Element<V>(value);
                ElemMap.put(value, elem);
                fatherMap.put(elem, elem);
                sizeMap.put(elem, 1);
            }

        }

        /**
         * 寻找某个元素所在集合的根节点，同时进行路径压缩优化，提高查询效率，知道什么叫做O(1)吗。
         * @param element
         * @return
         */
        private Element findHead(Element<V> element){
            //用栈，用队列，递归都可以。
            Deque<Element<V>> queue = new ArrayDeque<>();
            while(element != fatherMap.get(element)){
                queue.offer(element);
                element = fatherMap.get(element);
            }
            //摊还数据。并查集结构越用越快。
            while(!queue.isEmpty()){
                fatherMap.put(queue.poll(),element);
            }
            return element;
        }
        public boolean isSameSet(V a,V b){
            if(ElemMap.containsKey(a) && ElemMap.containsKey(b)){
                return findHead(ElemMap.get(a)) == findHead(ElemMap.get(b));
            }
            else {
                return false;
            }
        }
        public void union(V a, V b){
            //给定两个元素必须在对应的集合里
            if(ElemMap.containsKey(a) && ElemMap.containsKey(b)){
                //找最上面的根节点
                Element<V> aF = findHead(ElemMap.get(a));
                Element<V> bF = findHead(ElemMap.get(b));
                //不相交集合，开始合并，否则跳过直接往后返回。
                if(aF != bF){
                    //小的集合挂大的集合
                    //先假设最大，代码简单
                    Element<V> greater = sizeMap.get(aF) >= sizeMap.get(bF) ? aF:bF;
                    Element<V> less = greater == aF ? bF : aF;
                    //更新小集合的上集
                    fatherMap.put(less,greater);
                    //更新sizeMap的数据。
                    sizeMap.put(greater, sizeMap.get(aF) + sizeMap.get(bF));
                    sizeMap.remove(less);
                }
            }
        }
    }

}
